package G.二叉搜索树;

import java.util.*;

public class _235_二叉搜索树的最近公共祖先 {

    /**
     * 自解：因为所有结点都不一样 并且需要保存他的祖先 所以采取hashmap key取当前结点 value存父节点
     * 层次遍历依次存入hashmap 对hashmap进行遍历一直get套娃 直到得到的结点数值相等 返回结点
     * --因为两个node一个get可能会存在偏差 所以就对map进行遍历 一条线追溯所有祖先
     * ----耗时耗内存
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode,TreeNode> map = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();

        if (root == null){
            return root;
        }

        queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();

            while (size>0){
                TreeNode node = queue.poll();

                if (node.left != null){
                    map.put(node.left,node);
                    queue.add(node.left);
                }

                if (node.right != null){
                    map.put(node.right,node);
                    queue.add(node.right);
                }

                size--;
            }
        }

        List<TreeNode> list_p = new LinkedList<>();
        List<TreeNode> list_q = new LinkedList<>();
        list_p.add(p);
        list_q.add(q);
        //最终的跟结点肯定咩有父节点
        while (map.get(p) != null){

                list_p.add(map.get(p));//父节点加进去
                p= map.get(p);
        }
        while (map.get(q) != null){
            list_q.add(map.get(q));//父节点加进去
            q= map.get(q);
        }

        list_p.retainAll(list_q);
        return list_p.get(0);
    }

    /**
     * 题解：两次遍历
     * ----中序遍历的路径就是该结点的路径 遍历两个list 直到数值不想等就是出现分叉
     *
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> list_p = getPath(root,p);
        List<TreeNode> list_q = getPath(root,q);
        TreeNode ans = null;

        for (int i= 0;i<list_p.size() && i<list_q.size();i++){
            if (list_p.get(i) == list_q.get(i)){
                ans =list_p.get(i);
            }else {
                break;
            }
        }

        return ans;

    }
    //迭代法就行
    public List<TreeNode> getPath(TreeNode root,TreeNode node){
        List<TreeNode> rs = new LinkedList<>();

        while (root!= node ){//直接结点相等就行

            rs.add(root);
            if ( node.val < root.val){
                node = node.left;
            }else {
                node = node.right;
            }

        }
        rs.add(node);
        return  rs;
    }

    /**
     * 优化：通过遍历找出到达节点 pp 和 qq 的路径，一共需要两次遍历。我们也可以考虑将这两个节点放在一起遍历。
     *
     * 整体的遍历过程与方法一中的类似：
     *
     * 我们从根节点开始遍历；
     *
     * 如果当前节点的值大于 pp 和 qq 的值，说明 pp 和 qq 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
     *
     * 如果当前节点的值小于 pp 和 qq 的值，说明 pp 和 qq 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
     *
     * 如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，pp 和 qq 要么在当前节点的不同的子树中，要么其中一个就是当前节点。
     *

     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {

        while (true){
            if (p.val < root.val && q.val < root.val){
                root = root.left;
            }else if (p.val > root.val && q.val > root.val){
                root = root.right;
            }else {
                break;
            }
        }
        return root;
    }


}
